In satellite communications, mobile telecommunication systems, and the like, an error correction encoding technique exhibiting a large coding gain is being introduced in order to satisfy requirements in terms of system structures such as reduction of required power, reduction in the size of antennas, and the like. Particularly, low-density parity check codes are known as error correction codes that exhibit a large coding gain, and are being introduced in various types of communication systems for the satellite communications or the mobile telecommunication systems, and storage devices for magnetic recording.
The low-density parity check codes do not simply indicate a single error correction encoding method but is a general term for error correction codes having a characteristic that a check matrix is sparse (that most of components in a matrix are “0”, and the number of components “1” is extremely small). It is known that an error can be corrected by using an iterative decoding method such as a sum-product algorithm, a min-sum algorithm, or the like. It is known that by setting a particularly long frame length by selecting a sparse check matrix, a coding gain which is an indicator of an error correction performance can be made large (see Non-Patent Literatures 1 and 2, for example).
Setting a long frame length possibly enables a large coding gain to be obtained. However, there are also problems that the amount of calculation required for an encoding process for generating a parity bit and a decoding process for restoring original data from data in which an error is mixed is increased, and that the cost is increased. With respect to such problems, there is known a method of simplifying a process by causing a check matrix to have regularity, and such a low-density parity check code is called a quasi-cyclic low-density parity check code.
Mathematical formula 1 below shows a typical check matrix of the quasi-cyclic low-density parity check code.
                    H        =                  (                                                                      P                                      0                    ,                    0                                                                                                P                                      0                    ,                    1                                                                                                P                                      0                    ,                    2                                                                              …                                                              P                                      0                    ,                                          n                      -                      1                                                                                                                                            P                                      1                    ,                    0                                                                                                P                                      1                    ,                    1                                                                                                P                                      1                    ,                    2                                                                              …                                                              P                                      1                    ,                                          n                      -                      1                                                                                                                          ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                    ⋮                                            ⋮                                            ⋮                                                                                                                          ⋮                                                                                      P                                                            r                      -                      1                                        ,                    0                                                                                                P                                                            r                      -                      1                                        ,                    1                                                                                                P                                                            r                      -                      1                                        ,                    2                                                                              …                                                              P                                                            r                      -                      1                                        ,                                          n                      -                      1                                                                                                    )                                    [                  Mathematical          ⁢                                          ⁢          formula          ⁢                                          ⁢          1                ]            This check matrix is a block matrix of r×n (r and n are natural numbers (positive integers) satisfying r≦n), and in each component of the block matrix, Pi,j represents a zero matrix or a cyclic permutation matrix of m×m (m is a natural number, i is an integer between 0 and r−1, and j is an integer between 0 and n−1). The frame length of a quasi-cyclic low-density parity check code having the check matrix of Mathematical formula 1 is n×m.
The quasi-cyclic low-density parity check code may simplify the encoding process and the decoding process that uses the sum-product or min-sum algorithm by using the regularity of the check matrix of Mathematical formula 1 (the cyclicity of the component matrix Pi,j). Accordingly, the frame length may be increased while suppressing the complexity of the encoding and decoding processes by increasing a size m of the cyclic permutation matrix Pi,j (the size m is referred to as the number of stages). However, generally, with the low-density parity check code of such a structure, a large increase in the coding gain in accordance with the increase in the frame length cannot be expected. To increase the coding gain, it is desirable that n is made larger with respect to the number of stages m; however, in this case, there is a problem that the encoding and decoding processes are complicated in accordance with the increase in n.
As a technique related to the present application, Patent Literature 1 discloses a check matrix generation method adopting an LDGM (Low Density Generation Matrix) structure (paragraphs 0030, 0035, etc.), Patent Literature 2 discloses an error correction encoding method that uses low-density parity check codes (paragraph 0023, etc.), and Patent Literature 3 discloses a low-density parity check convolutional code (LDPC-CC) encoder (paragraphs 0048, etc.).